CF1267K Key Storage

神仙进制+组合数学+简单容斥题

妙不可言qwq！

题解：

本人能力有限，推荐这一篇：CSDN

截图防丢失：

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

#define int long long

const int N=21;
int c[N][N],cnt[N],n,m,ans;

int calc(int n){
    int res=1,sum=0;
    for(int i=n;i>=0;i--){
        if(!cnt[i]) continue;
        if(n-max(i,1ll)-sum<cnt[i]) return 0;
        res*=c[n-max(1ll,i)-sum][cnt[i]];
        sum+=cnt[i];
    }
    return res;
}

void doit(){
    read(n);
    for(int i=0;i<N;i++) cnt[i]=0;
    m=1;
    while(n){
        cnt[n%++m]++;
        n/=m;
    }
    ans=calc(m);
    if(cnt[0]) cnt[0]--,ans-=calc(m-1);
    write(ans-1);puts("");
}

void init(){
    for(int i=0;i<N;i++){
        c[i][0]=1;
        for(int j=1;j<=i;j++) c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
}

signed main(){
    int t;
    read(t);
    init();
    while(t--) doit();
}